//
// Created by black on 11/14/2024.
//

#ifndef TDTRPROCESS_LOCK_FREE_QUEUE_H
#define TDTRPROCESS_LOCK_FREE_QUEUE_H

#include <atomic>
#include <memory>
#include <iostream>

template<typename T>
class lock_free_queue
{
private:
    struct node;
    struct counted_node_ptr {
        int external_count;
        node* ptr;

        void print();
    };
    std::atomic<counted_node_ptr> head;
    std::atomic<counted_node_ptr> tail;
    struct node_counter {
        int internal_count;
        int external_counters;

        void print() {
            qDebug() << "internal_count = " << internal_count << ", external_counters = " << external_counters;
        }
    };


    struct node {
        std::atomic<T*> data;
        std::atomic<node_counter> count;
        std::atomic<counted_node_ptr> next;

        node() {
            node_counter new_count;
            std::memset(&new_count, 0, sizeof(node_counter));
            new_count.internal_count = 0;
            new_count.external_counters = 2;
            count.store(new_count);

            counted_node_ptr new_counted_node_ptr;
            std::memset(&new_counted_node_ptr, 0, sizeof(counted_node_ptr));
            new_counted_node_ptr.ptr = nullptr;
            new_counted_node_ptr.external_count = 0;
            next.store(new_counted_node_ptr);
            data = nullptr;
        }

        ~node() {

        }

        void print();

        void release_ref() {
            node_counter old_counter=
                    count.load(std::memory_order_relaxed);
            node_counter new_counter;
            do
            {
                new_counter = old_counter;
                --new_counter.internal_count;
            } while(!count.compare_exchange_strong(old_counter, new_counter, std::memory_order_acquire, std::memory_order_relaxed));
//            qDebug() << "release_ref";
//            new_counter.print();
            if(!new_counter.internal_count &&
               !new_counter.external_counters) {
//                qDebug() << "release_ref";
                delete this;
            }
        }
    };

    void set_new_tail(counted_node_ptr &old_tail, const counted_node_ptr &new_tail) {
        node* const current_tail_node = old_tail.ptr;
        while(!tail.compare_exchange_weak(old_tail, new_tail) && old_tail.ptr == current_tail_node);
        if(old_tail.ptr == current_tail_node) free_external_counter(old_tail);
        else current_tail_node->release_ref();
    }

    static void free_external_counter(counted_node_ptr &old_node_ptr) {
        node* const ptr = old_node_ptr.ptr;
        const int count_increase = old_node_ptr.external_count - 2;
        node_counter old_counter = ptr->count.load(std::memory_order_relaxed);
        node_counter new_counter;
        do {
            new_counter = old_counter;
            --new_counter.external_counters;
            new_counter.internal_count += count_increase;
        }
        while(!ptr->count.compare_exchange_strong(
                old_counter,new_counter,
                std::memory_order_acquire,std::memory_order_relaxed));
        if(!new_counter.internal_count &&
           !new_counter.external_counters) {
//            qDebug() << "deleted node from free_external_counter";
            delete ptr;
        }
    }

    static void increase_external_count(
            std::atomic<counted_node_ptr>& counter,
            counted_node_ptr& old_counter) {
        counted_node_ptr new_counter;
        do
        {
            new_counter = old_counter;
            ++new_counter.external_count;
        } while(!counter.compare_exchange_strong(
                old_counter,new_counter,
                std::memory_order_acquire, std::memory_order_relaxed));
        old_counter.external_count = new_counter.external_count;
    }


public:
    lock_free_queue() {
        counted_node_ptr new_next;
        std::memset(&new_next, 0, sizeof(counted_node_ptr));
        new_next.ptr = new node;
        new_next.external_count = 1;
        head.store(new_next);
        tail.store(new_next);
//        head.load().print();
    }

    ~lock_free_queue() {
        while(pop());
        delete tail.load().ptr;
    }

    lock_free_queue& operator=(const lock_free_queue&) = delete;
    lock_free_queue& operator=(lock_free_queue&&) = delete;

    bool empty() {
//        qDebug() << "empty start 0";
        counted_node_ptr old_head = head.load(std::memory_order_relaxed);
        increase_external_count(head,old_head);
//        qDebug() << "empty start 1";
        node* const ptr = old_head.ptr;
//        qDebug() << "empty start 2";
        bool r = (ptr == tail.load().ptr);
//        qDebug() << "empty: " << r;
//        qDebug() << "empty start 3";
        ptr->release_ref();
//        qDebug() << "empty end";
        return r;
    }

    std::unique_ptr<T> try_pop() {
        return pop();
    }

    bool try_pop(T& value) {
        std::unique_ptr<T> res = try_pop();
        if(res) value = *res;
        return res ? true : false;
    }


    std::unique_ptr<T> pop() {
        counted_node_ptr old_head_counted_node_ptr = head.load(std::memory_order_relaxed);
        for(;;)
        {
            increase_external_count(head, old_head_counted_node_ptr);
            node* const head_node_ptr = old_head_counted_node_ptr.ptr;
            if(head_node_ptr == tail.load().ptr)
            {
                head_node_ptr->release_ref();
                return std::unique_ptr<T>();
            }
            counted_node_ptr next_counted_node_ptr = head_node_ptr->next.load();
            if(head.compare_exchange_strong(old_head_counted_node_ptr, next_counted_node_ptr))
            {
                T * const res = head_node_ptr->data.exchange(nullptr);
//                qDebug() << "old_head in pop";
//                old_head_counted_node_ptr.print();
                free_external_counter(old_head_counted_node_ptr);
//                qDebug() << "new_head in pop";
//                head.load().print();
                return std::unique_ptr<T>(res);
            }
            head_node_ptr->release_ref();
        }
    }

//    void push(T new_value)
//    {
//        std::unique_ptr<T> new_data(new T(new_value));
//        counted_node_ptr new_next;
//        new_next.ptr = new node;
//        new_next.external_count = 1;
//        counted_node_ptr old_tail = tail.load();
//        for(;;)
//        {
//            increase_external_count(tail,old_tail);
//            T* old_data = nullptr;
//            if(old_tail.ptr->data.compare_exchange_strong(
//            old_data, new_data.get()))
//            {
//                old_tail.ptr->next = new_next;
//                old_tail = tail.exchange(new_next);
//                free_external_counter(old_tail);
//                new_data.release();
//                break;
//            }
//            old_tail.ptr->release_ref();
//        }
//        qDebug() << "push one node";
//        head.load().print();
//    }

    void push(T&& new_value)
    {
        std::unique_ptr<T> new_data(new T(std::forward<T>(new_value)));
        counted_node_ptr new_next_counted_node_ptr;
        std::memset(&new_next_counted_node_ptr, 0, sizeof(counted_node_ptr));
        new_next_counted_node_ptr.ptr = new node;
        new_next_counted_node_ptr.external_count = 1;
        counted_node_ptr old_tail_counted_node_ptr = tail.load();
        for(;;)
        {
            increase_external_count(tail, old_tail_counted_node_ptr);
            T* old_data = nullptr;
            if(old_tail_counted_node_ptr.ptr->data.compare_exchange_strong(
                    old_data,new_data.get()))
            {
                counted_node_ptr old_next_counted_node_ptr;
                std::memset(&old_next_counted_node_ptr, 0, sizeof(counted_node_ptr));
                old_next_counted_node_ptr.external_count = 0;
                old_next_counted_node_ptr.ptr = nullptr;
                if(!old_tail_counted_node_ptr.ptr->next.compare_exchange_strong(
                        old_next_counted_node_ptr, new_next_counted_node_ptr))
                {
                    delete new_next_counted_node_ptr.ptr;
                    new_next_counted_node_ptr = old_next_counted_node_ptr;
                }
                set_new_tail(old_tail_counted_node_ptr, new_next_counted_node_ptr);
                new_data.release();
                break;
            }
            else
            {
                counted_node_ptr old_next_counted_node_ptr;
                std::memset(&old_next_counted_node_ptr, 0, sizeof(counted_node_ptr));
                old_next_counted_node_ptr.external_count = 0;
                old_next_counted_node_ptr.ptr = nullptr;
                if(old_tail_counted_node_ptr.ptr->next.compare_exchange_strong(
                        old_next_counted_node_ptr, new_next_counted_node_ptr))
                {
                    old_next_counted_node_ptr = new_next_counted_node_ptr;
                    new_next_counted_node_ptr.ptr = new node;
                }
                set_new_tail(old_tail_counted_node_ptr, old_next_counted_node_ptr);
            }
        }
//        qDebug() << "push one node";
//        head.load().print();
    }
};

template<typename T>
void lock_free_queue<T>::node::print() {
    qDebug() << "data = " << data.load();
    qDebug() << "count: ";
    count.load().print();
    qDebug() << "next: ";
    next.load().print();
}

template<typename T>
void lock_free_queue<T>::counted_node_ptr::print() {
    qDebug() << "external_count = " << external_count;
    if(ptr) {
        qDebug() << "ptr: " << ptr;
        ptr->print();
    }
    else qDebug() << "ptr: nullptr";
}

#endif //TDTRPROCESS_LOCK_FREE_QUEUE_H